The invention relates generally to switching implemented in a packet-switched telecommunications network. More particularly, the invention relates to a switch arrangement used in such a network, specifically an ATM network.
To aid the understanding of the following description, some terms to be used later will first be defined.
A switching fabric or switching matrix (both terms are used) is comprised of a plurality of switching elements which are either identical or dissimilar and are interconnected according to a given topology. In the (English-language) literature of the art, such a switching matrix may also be called a xe2x80x9cswitching networkxe2x80x9d, since the switching elements form a network having the given topology. Hence, a switching matrix is considered to have a defined form when its switching elements and their interconnections are known.
A switching fabric is composed of switching elements by connecting a number of switching elements into a network comprising switching elements in parallel and in succession. Parallel switching elements make up one switching stage. Switching elements in successive switching stages are interconnected by internal links in accordance with the above topology.
The term switch is used to denote the entity configured about a switching matrix. Hence, a switch can denote any means employed for signal switching in a telecommunications network. In the present context, a switch is a packet switch as the invention is related to switching in a packet-switched telecommunications network, particularly an ATM network. A switch is also sometimes termed a switching system.
ATM (Asynchronous Transfer Mode) is a connection-oriented packet-switching technique, which has been selected by the international organization for telecommunications standardization, ITU-T, as the target transfer mode solution for implementing a broadband multimedia network (B-ISDN). In an ATM network, the problems of conventional packet-switched networks (such as X.25 networks) are overcome by transmitting short packets of a constant length (53 bytes) called cells. Each cell comprises a 48-byte payload portion and a 5-byte header. The header comprises, along with other data, address information on the basis of which the cell is routed in an ATM network. Further discussion of an ATM network herein will be omitted as non-essential subject to the understanding of the invention. When required, a closer description of this topic can be found in international standards and textbooks of the art.
Switches in a conventional TDM network (Time Division Multiplexing, also called by the name STM, Synchronous Transfer Mode) cannot be directly implemented to handle the switching in an ATM network. Neither are the switching solutions developed for conventional packet networks usually suitable as switches for an ATM network. The selection of an optimum ATM switching architecture is namely influenced not only by the fixed cell size and the limited functionality of the cell header but also by the statistical behaviour of the cell stream and the fact that an ATM switch must operate at a very high rate (currently typically about 150 . . . 600 Mbit/s).
FIG. 1 shows schematically an ATM switch seen from the outside. The switch has n input lines I1 . . . In and m output lines O1 . . . Om. A cell stream CS arrives over each input line to the ATM switch 11. The header of an individual cell in the cell stream is denoted by reference HD. In the ATM switch, the cells are switched from the input line Ii to the output line O1, and simultaneously the value of the cell header is translated from an incoming value to an outgoing value. For this purpose, the switch includes a translation table 12 by means of which said translation is made. It is to be seen from the table that, for example, all the cells received over line I1 and having a header with a value X are switched onto output port O1 whereby their header is simultaneously given the value K. Cells present on different input lines may have headers of equal value; for example, cells received at input line In with the same header value X are also switched onto output line O1, but their header is given the value J on the output line.
A prior art header translation method, which will be used in describing the present invention, is to translate the header in steps by using unique connection identifiers internal to the switch, such as the identifier ICI on the input side and the identifier ECI on the output side. In that case, the header translation chain will be VPIin/VCIinxe2x86x92ICIxe2x86x92ECIxe2x86x92VPIout/VCIout. The advantage of such a procedure is that the identifiers ICI and ECI can be direct memory addresses by means of which the connection-related data can be rapidly accessed.
Hence, the main tasks of a switch are: transfer of cells (packets) from the input line to the desired output line, and header translation. Occasionally, however, as is also evident from the figure, two cells may be simultaneously contending for access onto the same output line. For this purpose, the switch must have buffering capacity to avoid the necessity of discarding cells in such a situation. Hence, the third main task of a switch is to provide buffering. The manner in which these three main tasks are performed and in which part of the switch the implementation is handled distinguishes different switching solutions from one another.
ATM switching fabrics, on the other hand, can be subdivided into two classes depending on whether the switching elements used in the fabric are buffered or unbuffered.
In a fabric using unbuffered switching elements, routing of cells through the fabric operates at the cell level in such a way that a route is separately selected for each cell irrespective of which virtual channel the cell belongs to. In simplified rendition, proceeding of cells through the fabric may be thought of as comprising two steps. In the first step, the cells are sent from the input ports through the fabric, and in the second step either the switching elements or the output ports give an indication to the input port which cells were successful in traversing the fabric. The latter step must be performed, since if the cells possibly attempt to use the same internal link of the fabric, all simultaneous cells except one must be discarded since the switching elements have no buffers. The problem with such a switching fabric is that the operation of all its elements must be mutually synchronized, i.e., all elements and input and out-put ports must be in the above-described steps at the same time. Since cell transmission is very rapid and in practice even several further steps may be necessary besides the two described above, synchronization cannot be achieved merely by means of handshaking signals between the elements, but all elements must be synchronized from a common clock source, and it is difficult to distribute the clock signal to all elements if the switching fabric is very broad and it has been necessary to divide it among several plug-in units. It may also be noted that even a switch provided with non-buffered switching elements must have buffering capacity either in the input or in the output ports of the fabric to avoid the need of discarding cells contending simultaneously for the same output line of the switch.
A switching fabric comprised of buffered switching elements does not have the above synchronizing requirement. The selection of the route of the cells through the switching fabric can be virtual channel-related. For this purpose, however, a record of the load on the internal links of the switching fabric must usually be kept. A buffered switching fabric is usually blocking at the connection level, as to construct it to be non-blocking usually requires so much extra capacity that this is no longer economically feasible. In a blocking fabric, the selection of the route for the connection is a highly critical factor when it is attempted to reduce the blocking.
On account of the foregoing, many manufacturers have sought a solution from a method in which the route is selected at the cell level also in a switching fabric provided with buffered switching elements. To avoid the necessity of keeping a record of the load on the internal links of the fabric and to enable even distribution of the load, the cell route is usually selected at random. (The selection may also be done in accordance with a suitable non-random algorithm.) In that case, the switching fabric can be constructed to be non-blocking at reasonable cost.
Since the route of the cells varies in such random routing, it is possible that a cell sent later travels faster through the switching fabric and overtakes a cell sent earlier. This is due to the fact that the load on the switching elements and thereby also the fill rates of their buffers vary constantly, and hence also the dwell time of the cell in the fabric varies at different times and over different routes. Restoring the order of the cells necessitates special solutions known as re-sequencing.
In principle, there are two basic solutions for cell re-sequencing depending on which part of the switching fabric the re-sequencing is performed in. The cells can be re-sequenced either after the switching fabric in re-sequencing (micro)circuits provided for this purpose (alternative 1), or the re-sequencing can be performed already within the switching fabric between its switching stages (alternative 2).
The factor common to the above solutions is that the transit time used by the cell in traversing the switching fabric (alternative 1) or to the switching elements (alternative 2) is measured for example by using a time stamp, and thereafter the cell is delayed for a time sufficient for a predetermined total transit time to be exceeded. This ensures that the delay of all cells through the switching fabric remains the same. The drawback of these solutions, however, is that they require a very complex circuit using parallel processing at the output ports of the switching fabric (alternative 1) or in the switching elements (alternative 2).
One re-sequencing implementation relating to alternative 1 is disclosed in U.S. Pat. No. 5,481,536. This solution utilizes serial numbers for cells, by means of which the relative order of the cells over the same connection can be inferred. The cells are written into a common memory, and the addresses by means of which cells are read out from the common memory are searched from a content addressable memory (CAM).
Also this solution has complex implementation and requires a special memory (CAM) that is not equal to conventional (fast) memories in terms of retrieval times and cost.
U.S. Pat. Nos. 5,319,360 and 5,173,897, on the other hand, disclose an ATM node in which the cells on a virtual connection also have a serial number by means of which the relative order of the cells is identified. In the output unit between the switching fabric and the output port of the node, the cells are stored in a memory at the head of which a shift register section is provided, followed by a first FIFO unit. A cell is read out from the head of the queue onto a latch wherefrom the cell is further read out from the node. Prior to reading out from the latch, the connection identifier of the cell on the latch is compared with the connection identifiers of all other cells in the shift register section and the FIFO units, and an additional comparison is carried out on all cells having the same connection identifier as the cell on the latch, in which comparison the serial numbers of these two cells are compared. If the cell in the memory turns out to be older, it replaces the cell on the latch and the cell on the latch is transferred back to the memory to replace the older cell. In this way, the oldest stored cell pertaining to said connection is obtained as the cell to be transferred.
The drawbacks of this solution include a very complex memory arrangement and the heavy comparison process it requires to find the oldest stored cell in each case.
It is an object of the present invention to eliminate the drawbacks described above and to provide a method wherewith the re-sequencing of packets can be implemented with as simple equipment as possible without any heavy comparison process.
This object is achieved with a solution as defined in the independent claim.
The invention utilizes a basic solution as described above, in which each packet (or cell) over the connection has an order stamp that is a serial number by means of which the cells on the connection can be ordered in the correct sequence. Furthermore, the invention utilizes a basic solution maintaining a serial number for an anticipated packet. The idea is to store the packet or the information relating thereto (e.g. a memory pointer) in a memory area that is dependent on at least the serial number of the packet in accordance with a given predetermined relationship. This is done at least every time it is detected on the basis of the anticipated serial number that the order of the packets has changed. The packet may also be transferred directly to the output buffer if the serial number of the incoming packet corresponds to the serial number of the anticipated packet (that is, if order of the packets has not changed). By performing the storing in a memory area dependent on the serial number of the packet, at least each time packets are not being received a packet to be transferred to a buffer (or its memory pointer) can be searched from the memory area that is dependent on the current anticipated serial number in accordance with the same relationship.
In a particularly preferred embodiment of the invention, storage in memory takes place in a memory area defined merely on the basis of the serial number of the packet and reading out from the memory from a memory area defined merely on the basis of the anticipated serial number. In this way, the memory capacity required can be minimized.